import java.util.Stack;

/**
 * 面试题 03.05. 栈排序
 * https://leetcode-cn.com/problems/sort-of-stacks-lcci/
 */
public class Solutions_mianshi_03_06 {
    public static void main(String[] args) {
        SortedStack obj = new SortedStack();
        obj.push(1);
        obj.push(2);
        int res1 = obj.peek();  // output: 1
        System.out.println(res1);
        obj.pop();
        int res2 = obj.peek();  // output: 2
        System.out.println(res2);
    }
}

/**
 * 解法二：stack 保证栈中元素升序（栈顶元素最小），help 保证栈中元素降序（栈顶元素最大）
 */
class SortedStack {
    Stack<Integer> stack = new Stack<>();;
    Stack<Integer> help = new Stack<>();;

    public SortedStack() {

    }

    public void push(int val) {
        while (!stack.isEmpty() && stack.peek() < val) {
            help.push(stack.pop());
        }
        // 优化：不是每次 push 时都将 help 里的元素，都 push 到 stack 里
        while (!help.isEmpty() && help.peek() > val) {
            stack.push(help.pop());
        }
        stack.push(val);
    }

    public void pop() {
        // 弹出最小值时，将 help 中的小值，push 到 stack 中
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
        if (!stack.isEmpty()) {
            stack.pop();
        }
    }

    public int peek() {
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
        if (stack.isEmpty()) {
            return -1;
        }
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty() && help.isEmpty();
    }
}

/**
 * 解法一：建立辅助栈，保证 push 进的元素，在 stack 栈的栈顶（214ms）
 */
class SortedStack2 {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> help = new Stack<>();

    public SortedStack2() {

    }

    public void push(int val) {
        // 通过辅助栈 help 保证 stack 中较小的元素在栈顶，较大的元素在栈底
        while (!isEmpty() && val > peek()) {
            help.push(stack.pop());
        }
        stack.push(val);
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }

    public void pop() {
        if (!isEmpty()) {
            stack.pop();
        }
    }

    public int peek() {
        return isEmpty() ? -1 : stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}
